package my.jwds.p420;

import java.util.*;

public class StrongPasswordChecker {

    public static void main(String[] args) {

        StrongPasswordChecker obj = new StrongPasswordChecker();
        long start = System.currentTimeMillis();
        System.out.println(obj.strongPasswordChecker("ABABABABABABABABABAB1"));
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }




    public int strongPasswordChecker(String password) {

        int[]nums = new int[4];
        List<Integer> riffs = new LinkedList<>();
        char prev = '`';
        int length = 0;
        for (int i = 0; i < password.length(); i++) {
            char now = password.charAt(i);
            int type = 3;
            if (now >= '0' && now <= '9'){
                type = 0;
            }else if (now >= 'a' && now <= 'z'){
                type = 1;
            }else if (now >= 'A' && now <= 'Z'){
                type = 2;
            }
            nums[type]++;
            if (prev != now || password.length() == i+1){
                if (prev == now)length++;
                if (length >= 3){
                    riffs.add(length);
                }
                prev = now;
                length = 1;
            } else{
                length++;
            }

        }

        Collections.sort(riffs, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1%3+1 - (o2%3+1);
            }
        });


        int removeOperation = 0;
        int addOrEditOperation = 0;
        int residue = password.length();


        while(residue > 20 && !riffs.isEmpty()){
            LinkedList<Integer> newRiffs = new LinkedList<>();
            for (Integer riff : riffs) {
                int diff = riff%3+1;
                if (residue - diff < 20){
                    removeOperation += residue - 20;
                    residue = 20;
                    riff -= residue - 20;
                }else{
                    removeOperation += diff;
                    residue-=diff;
                    riff -= diff;
                }
                if (riff >=3){
                    newRiffs.addFirst(riff);
                }
            }
            riffs = newRiffs;
        }



        if (residue > 20){
            removeOperation += residue - 20;
        }

        for (Integer riff : riffs) {
            addOrEditOperation += riff/3;
            if (residue < 6){
                residue+= riff/3;
            }
        }



        if (residue < 6){
            addOrEditOperation += 6-residue;
        }

        int lack = 0;
        for (int i = 0; i < 3; i++) {
            if (nums[i] == 0)lack++;
        }
        if (lack > addOrEditOperation){
            addOrEditOperation = lack;
        }
        return removeOperation + addOrEditOperation;

    }
}